package org.chnxi.leetcode.problems.ques21;

/**
 * 合并两个有序链表
 * 执行用时 :1 ms, 在所有 Java 提交中击败了62.86%的用户
 * 内存消耗 :39.7 MB, 在所有 Java 提交中击败了42.05%的用户
 */
public class Simple01 {

    public static void main(String[] args) {
        ListNode l1_1 = new ListNode(1);
        ListNode l1_2 = new ListNode(2);
        ListNode l1_3 = new ListNode(4);
        l1_1.next = l1_2;
        l1_2.next = l1_3;

        ListNode l2_1 = new ListNode(1);
        ListNode l2_2 = new ListNode(3);
        ListNode l2_3 = new ListNode(4);
        l2_1.next = l2_2;
        l2_2.next = l2_3;

        ListNode result =  mergeTwoLists(null , null);
        System.out.println(result);
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //记录最终结果值，默认先创建一个节点，返回时需要从下个节点返回
        ListNode result = new ListNode(0);

        //记录当前操作next的节点
        ListNode curNode = result;

        do{
            //如果两个链表都为空，表示已经循环到最长链表最后，可退出循环
            if(l1 == null && l2 == null){
                break;
            }

            //获取当前节点的值
            int val1 = l1 == null ? Integer.MAX_VALUE : l1.val;
            int val2 = l2 == null ? Integer.MAX_VALUE : l2.val;

            //获取较小的值，并让链表进行滚动到next，用于执行下次循环使用
            //需要处理null的情况
            ListNode minNode = null;
            if(val1 <= val2){
                minNode = new ListNode(val1);
                l1 = l1 == null ? null : l1.next == null ? null : l1.next;
            }else{
                minNode = new ListNode(val2);
                l2 = l2 == null ? null : l2.next == null ? null : l2.next;
            }
            //将较小的值加入到结果链表，并移动当前操作节点
            curNode.next = minNode;
            curNode = minNode;

        }while (l1 != null || l2 != null);

        return result.next;
    }

}
